import org.junit.Test;

import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * Package: PACKAGE_NAME
 * Created by OriKey on 2020/9/2.
 * --- 平凡才是唯一的答案 ---
 */
public class FirstProblem {
    /*
     * 题目要求：实现一个这样的函数，函数要求输入的正整数N，来返回其所有小于N的素数列表
     *个人思考：
     *     需要考虑以下几点：
     *               ①时间开销
     *               ②空间开销
     *               ③非法输入
     *               ④数值过大
     *主要思路：
     *   ①一般解决方案，遍历从[2,sqrt(N)+1)中的所有数字，如果有数字可以整除N，那么该数不是质数，
     *   如果没有数字可以整除N，那么该数为正整数。
     *   优点：实现简单，在N不是特别大的情况和单次输入的情况下，时间和空间效率都是可以被接受的。
     *   缺点：时间复杂度较高，不能够复用计算过的
     *
     *   ②基于6N原则进行计算，时间效率大概为思路一的总效率的一倍左右，本题目在考虑到实现以及单机应用，
     *   将实现该方法。
     *
     *   ③使用筛法，可以基于欧拉筛和线性筛法，由于数组大小关系，将没有办法在给定空间内实现Long大小应用。
     *
     *   ④其他：个人觉得，如果这部分内容经常使用的话，可以在内部一定范围中建立Redis模型，把数值和是否是存储起来，
     *   通过离线存储的方式进行操作之后只需要使用get来判断是否是质数即可，如果数值过大，则可以使用Π函数估计。
     * 最终方案：
     *
     * */
    public static List<Integer> getPrime(Long N) {
        int[] arr;
        List<Integer> res = new LinkedList<>();
        //首先判断非法输入
        if (N <= 0) {
            System.out.println("输入非法");
            return null;
        }
        //使用筛法判断。
        if (N >= 10000000 && N <= Integer.MAX_VALUE) {
            int n = Long.valueOf(N).intValue();

            boolean[] array;
            try {
                array = new boolean[n];
                for (int i = 2; i < n; i++) {
                    array[i] = true;
                }
                for (int i = 2; i < n; i++) {
                    if (array[i]) {
                        int j, temp;
                        temp = i;
                        for (j = 2 * temp; j < n; j = j + temp) {
                            array[j] = false;
                        }
                        res.add(i);
                    }
                }
            } catch (OutOfMemoryError e) {
                System.out.println("您的空间大小不足，将自动退化到一般解法，可能需要较长时间");
                for (int i = 2; i < N; i++) {
                    if (isPrime(i)) {
                        res.add(i);
                    }
                }
            }

        } else {
            for (int i = 2; i < N; i++) {
                if (isPrime(i)) {
                    res.add(i);
                }
            }
        }

        return res;

    }

    //高效判断素数，基于6N原则实现
    private static boolean isPrime(int num) {
        if (num == 2 || num == 3) {
            return true;
        }

        //如果不在6的倍数附近，肯定不是素数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        //对6倍数附近的数进行判断
        for (int i = 5; i <= Math.sqrt(num); i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) throws FileNotFoundException {


        //1千万数值会是一个比较好的测试样例，如果数值过大的话由于没用使用筛法，将导致较长的运行时间。
        System.out.println("请输入数值：");
        Scanner in = new Scanner(System.in);
        Long N = in.nextLong();
        in.nextLine();
        if (N >= 10000000) {
            System.out.println("您输入的值较大，我们将采用筛法来进行判断，这可能会有较高的额外空间开销.");
        } else if (N >= Integer.MAX_VALUE) {
            System.out.println("您输入的值过大，可能需要很长的时间才能得到结果");
        }
        List<Integer> arr = getPrime(N);
        if (arr == null) {
            System.out.println("NULL");
            return;
        }
        System.out.println("计算完成，您希望将结果输入到文件中去吗？Y/N");
        String s = in.nextLine();
        if (s.equals("Y")) {
            PrintStream out = new PrintStream("Result/Res.txt");
            System.out.println("您将会在Result/Res.txt文件中看到结果");
            System.setOut(out);
        } else if (s.equals("N")) {
            System.out.println("您将会在命令行中看到结果");
        } else {
            System.out.println("输入有误，默认命令行输出");
        }
        System.out.println(Arrays.toString(arr.toArray()));
    }
}
